function gewQuadTree(half_size,leaf_half_size)
{
  this.columnNum = this.rowNum = half_size/leaf_half_size;
  this.cell = []; 
  this.halfSize = half_size;
  this.size = half_size*2;
  this.leafHalfSize = leaf_half_size;
  this.leafSize = leaf_half_size*2;
  this.root = new gewQuadTreeNode(this,null,0,0,leaf_half_size, half_size);
}
gewQuadTree.prototype = {
  getCellAt:function(x,z)
  {
    var col = Math.floor((x+this.halfSize)/this.leafSize);
    var row = Math.floor((z+this.halfSize)/this.leafSize);
    return this.cell[col+row*this.columnNum];
  },
  getRow:function(x,z)
  {
    return Math.floor((z+this.halfSize)/this.leafSize);
  },
  getColumn:function(x,z)
  {
    return Math.floor((x+this.halfSize)/this.leafSize);
  },
  viewFrustumCulling:function(frustum)
  {
    var root = this.root;
    root.branch0.viewFrustumCulling(frustum);
    root.branch1.viewFrustumCulling(frustum);
    root.branch2.viewFrustumCulling(frustum);
    root.branch3.viewFrustumCulling(frustum);
  },
  collisionWithRay:function(ray,outCells,maxDistance)
  {
    this.root.collisionWithRay(ray,outCells,maxDistance)
  }
}
function gewQuadTreeNode(tree,parent,center_x,center_z,leaf_half_size, half_size)
{
  this.id = 0;// id in cell list ( only use in leaf node )
  this.isInFrustum = false; // is in view frustum or not
  this.tree = tree;
  this.parent = parent;
  if(parent)
    this.halfSize = parent.halfSize/2;
  else
    this.halfSize = half_size;
  this.minX = center_x-this.halfSize;
  this.maxX = center_x+this.halfSize;
  this.minZ = center_z-this.halfSize;
  this.maxZ = center_z+this.halfSize;
  gewRegVec0.set(this.minX,0,this.minZ);
  gewRegVec1.set(this.maxX,0,this.maxZ);
  this.aabb = new gewAabb(gewRegVec0,gewRegVec1);
  this.nodeList = []; // scene node list that in this quad node ( only use in quad leaf node)
  if(this.halfSize>leaf_half_size)
  {
    var qSize = this.halfSize/2;
    this.branch0 = new gewQuadTreeNode(tree,this,center_x-qSize,center_z-qSize,leaf_half_size);
    this.branch1 = new gewQuadTreeNode(tree,this,center_x+qSize,center_z-qSize,leaf_half_size)
    this.branch2 = new gewQuadTreeNode(tree,this,center_x-qSize,center_z+qSize,leaf_half_size)
    this.branch3 = new gewQuadTreeNode(tree,this,center_x+qSize,center_z+qSize,leaf_half_size)
  }  
  else
  {
    var column = (this.minX+tree.halfSize)/(leaf_half_size*2);
    var row = (this.minZ+tree.halfSize)/(leaf_half_size*2);
    this.id = Math.round(column+ row*tree.columnNum);
    tree.cell[this.id] = this;
  }
  // PRIVATE:
  this.freeIdx = [];// Free idx table to insert scene node
}
gewQuadTreeNode.prototype = {
  // Return all cell that collision with the ray 
  collisionWithRay:function(ray,outCells,maxDistance)
  {
    var b0 = this.branch0;
    var b1 = this.branch1;
    var b2 = this.branch2;
    var b3 = this.branch3;
    var isCollision0 = ray.colisionWithAabb(b0.aabb,maxDistance);
    var isCollision1 = ray.colisionWithAabb(b1.aabb,maxDistance);
    var isCollision2 = ray.colisionWithAabb(b2.aabb,maxDistance);
    var isCollision3 = ray.colisionWithAabb(b3.aabb,maxDistance);
    var isLeaf = (b0.branch0==undefined);
    if(isLeaf)
    {
      if(isCollision0)
        outCells.push(b0);
      if(isCollision1)
        outCells.push(b1);
      if(isCollision2)
        outCells.push(b2);
      if(isCollision3)
        outCells.push(b3);      
    }
    else
    {
      if(isCollision0)
        b0.collisionWithRay(ray,outCells,maxDistance);
      if(isCollision1)
        b1.collisionWithRay(ray,outCells,maxDistance);
      if(isCollision2)
        b2.collisionWithRay(ray,outCells,maxDistance);
      if(isCollision3)
        b3.collisionWithRay(ray,outCells,maxDistance);
    }
  },
  getFreeIndex:function()
  {
    return this.freeIdx.pop();
  },
  updateAabb:function(nodeAabb)
  {
    var aabb = this.aabb;
    var isUpdate = false;
    if(aabb.min.y==0&&aabb.max.y==0)
    {
      aabb.min.y = nodeAabb.min.y;
      aabb.max.y = nodeAabb.max.y;
      isUpdate=true;
    }
    else
    {
      if(aabb.min.y> nodeAabb.min.y)
      {
        aabb.min.y = nodeAabb.min.y;
        isUpdate=true;
      }
      if(aabb.max.y< nodeAabb.max.y)
      {
        aabb.max.y = nodeAabb.max.y;
        isUpdate=true;
      }
    }
    if(isUpdate&&this.parent)
      this.parent.updateAabb(nodeAabb);
  },
  removeNode:function(node,cellIdx)
  {
    var nodeIdx = node.quadTreeIdx[cellIdx];
    this.nodeList[nodeIdx] = null;
    this.freeIdx.push(nodeIdx);
    node.quadTreeCells.splice(cellIdx,1);
    node.quadTreeIdx.splice(cellIdx,1);
    if(node.physicsBody)
      node.physicsBody.removeFromCell(this);
    //console.log("Remove node '"+node.name+"' from cell:"+this.id);
  },
  addNode:function(node)
  {
    node.quadTreeCells.push(this);
    this.updateAabb(node.worldAabb);
    var idx = this.getFreeIndex();
    if(idx==undefined)
      idx = this.nodeList.length;
    this.nodeList[idx] = node;
    node.quadTreeIdx.push(idx);
    if(node.physicsBody)
      node.physicsBody.addToCell(this);
    //console.log("Add node '"+node.name+"' into cell:"+this.id);
  },
  setInFrustum:function(value)
  {
    this.isInFrustum = value;
    if(this.branch0)
    {
      this.branch0.setInFrustum(value);
      this.branch1.setInFrustum(value);
      this.branch2.setInFrustum(value);
      this.branch3.setInFrustum(value);
    }
    else // leaf node
    {
      if(value)
      {
        var sceneNodeList = this.nodeList;
        var len = sceneNodeList.length;
        for(var i =0;i<len;i++)
        {
          var sceneNode = sceneNodeList[i];
          if(sceneNode)
            sceneNode.setFlag(NODE_FRUSTUM_IN|NODE_FRUSTUM_TESTED,true); 
        }
      }
    }
  },
  viewFrustumCulling:function(frustum)
  {
    var test = frustum.isContainAabb(this.aabb);
    switch(test)
    {
      case GEW_IN:
        this.setInFrustum(true);
        return;
      case GEW_OUT:
        return;
      case GEW_INTERNAL:
      case GEW_INTERSECT:
        this.isInFrustum=true;
        if(this.branch0)
        {
          this.branch0.viewFrustumCulling(frustum);
          this.branch1.viewFrustumCulling(frustum);
          this.branch2.viewFrustumCulling(frustum);
          this.branch3.viewFrustumCulling(frustum);
        }
        else // leaf node
        {
          var sceneNodeList = this.nodeList;
          var len = sceneNodeList.length;
          for(var i =0;i<len;i++)
          {
            var sceneNode = sceneNodeList[i];
            if(sceneNode)
              sceneNode.viewFrustumCulling(frustum); 
          }
        }
        return;
      default:
        alert('gewQuadTree:viewFrustum:error! it should not run here!')
        return;
    }
  }
}
